import java.util.*;

public class Test {
    // 题目 1：非递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        TreeNode pre = null;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if(node.right == null || node.right == pre){
                list.add(node.val);
                pre = node;
                node = null;
            }else{
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }

    // 题目2：二叉树以前序遍历的顺序展开为链表
    // 方法一：迭代版本
    public void flatten1(TreeNode root) {
        TreeNode node = root;
        while(node != null){
            TreeNode move = node.left;
            if(move != null){
                while(move.right != null){
                    move = move.right;
                }
                move.right = node.right;
                node.right = node.left;
                node.left = null;
            }
            node = node.right;
        }
    }

    // 方法二：递归
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        flatten(root.left);
        TreeNode Right = root.right;
        root.right = root.left;
        root.left = null;
        while(root.right != null){
            root = root.right;
        }
        root.right = Right;
        flatten(root.right);
    }

    // 题目3：二叉树的右视图
    int depth;
    List<Integer> list = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        height(root, 1);
        return list;
    }
    private void height(TreeNode root, int h){
        if(root == null){
            return ;
        }

        if(h > depth){
            depth = h;
            list.add(root.val);
        }

        height(root.right, h + 1);
        height(root.left, h + 1);
    }

    // 题目4：求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return dsf(root, 0);
    }

    private int dsf(TreeNode root, int pre){
        if(root == null){
            return 0;
        }

        int sum = pre * 10 + root.val;

        int left = dsf(root.left, sum);
        int right = dsf(root.right, sum);

        if(left == 0 && right == 0){
            return sum;
        }else{
            return left + right;
        }
    }

    // 题目5： 有序链表转换二叉搜索树
    public TreeNode sortedListToBST(ListNode head) {
        return createTree(head, null);
    }

    private TreeNode createTree(ListNode left, ListNode right){
        if(left == right){
            return null;
        }

        ListNode mid = getMid(left, right);
        TreeNode node = new TreeNode(mid.val);

        node.left = createTree(left, mid);
        node.right = createTree(mid.next, right);
        return node;
    }

    private ListNode getMid(ListNode left, ListNode right){
        ListNode fast = left;
        ListNode slow = left;

        while(fast != right && fast.next != right){
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    // 题目6：恢复二叉搜索树
    // 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
    public void recoverTree1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        inorder(root,list);
        int[] nums = getWrongNums(list);
        cover(root, 2, nums[0], nums[1]);
    }

    private void inorder(TreeNode root, List<Integer> list){
        if(root == null){
            return ;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    private int[] getWrongNums(List<Integer> list){
        int index1 = -1;
        int index2 = -1;
        int n = list.size();
        for(int i = 0; i < n - 1; i++){
            if(list.get(i + 1) < list.get(i)){
                index2 = i + 1;
                if(index1 == -1){
                    index1 = i;
                }else{
                    break;
                }
            }
        }
        int x = list.get(index1);
        int y = list.get(index2);

        return new int[]{x,y};
    }

    private void cover(TreeNode root, int count, int x, int y){
        if(root == null){
            return;
        }
        if(root.val == x || root.val == y){
            root.val = root.val == x ? y : x;
            if(--count == 0){
                return;
            }
        }
        cover(root.left, count, x, y);
        cover(root.right, count, x, y);
    }

    // 方法二：非递归中序遍历，无需使用额外的列表来存储中序遍历顺序，在一次中序遍历中找到两个异常节点，进行交换即可。
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode x = null, y = null, pre = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if(pre != null && root.val < pre.val){
                y = root;
                if(x == null){
                    x = pre;
                }else{
                    break;
                }
            }
            pre =root;
            root = root.right;
        }
        swap(x, y);
    }

    private void swap(TreeNode x, TreeNode y){
        int num = x.val;
        x.val = y.val;
        y.val = num;
    }

    // 题目 7：出现次数最多的子树元素和
    // 给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
    //
    //一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
    Map<Integer, Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        treeSum(root);
        int max = -0x3f3f3f3f;
        for(Integer x : map.values()){
            max = Math.max(max, x);
        }
        List<Integer> list = new LinkedList<>();
        for(Integer x : map.keySet()){
            if(map.get(x) == max){
                list.add(x);
            }
        }

        int[] nums = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            nums[i] = list.get(i);
        }

        return nums;
    }

    private int treeSum(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = treeSum(root.left);
        int right = treeSum(root.right);

        int sum = left + right + root.val;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        return sum;
    }

    // 可修改如下
    Map<Integer, Integer> map1 = new HashMap<>();
    int max1 = -0x3f3f3f3f;
    public int[] findFrequentTreeSum1(TreeNode root) {
        treeSum1(root);
        List<Integer> list = new LinkedList<>();
        for(Integer x : map1.keySet()){
            if(map1.get(x) == max1){
                list.add(x);
            }
        }
        int[] nums = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            nums[i] = list.get(i);
        }
        return nums;
    }

    private int treeSum1(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = treeSum(root.left);
        int right = treeSum(root.right);

        int sum = left + right + root.val;
        map1.put(sum, map1.getOrDefault(sum, 0) + 1);
        max1 = Math.max(max1, map1.get(sum));
        return sum;
    }


    // 题目8：把二叉搜索树转换为累加树
    // 给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);

        }
        return root;
    }

    // 题目 9 ：两棵二叉搜索树中的所有元素
    // 同时中序遍历两个搜索二叉树，这解法太牛了！
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();

        while(root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()){
            while(root1 != null){
                stack1.push(root1);
                root1 = root1.left;
            }

            while(root2 != null){
                stack2.push(root2);
                root2 = root2.left;
            }

            if(stack1.isEmpty()){
                root2 = stack2.pop();
                list.add(root2.val);
                root2 = root2.right;
                continue;
            }

            if(stack2.isEmpty()){
                root1 = stack1.pop();
                list.add(root1.val);
                root1 = root1.right;
                continue;
            }

            if(stack1.peek().val < stack2.peek().val){
                root1 = stack1.pop();
                list.add(root1.val);
                root1 = root1.right;
            }else{
                root2 = stack2.pop();
                list.add(root2.val);
                root2 = root2.right;
            }
        }
        return list;
    }


}
